Data Structure--Binary search trees

Definition. A BST is a binary tree in symmetric order

A binary tree is either: ・Empty. ・Two disjoint binary trees (left and right).

Symmetric order. Each node has a key,

and every node’s key is: ・Larger than all keys in its left subtree. ・Smaller than all keys in its right subtree.

Java definition A BST is a reference to a root Node.

A Node is comprised of four fields:

A key and A vaule.

A reference to the left and right subtrees


public class Node{
	private Key key;
	private Vaule val；
	private Node left,right;
	private int count;//for size()
	private Node(Key key,Vaule val){
		this.key=key;
		this.vaule=val;
	}
}

BST implementation(Skeleton)


public class BST<Key extends Comparable<Key>,Vaule>{
	private Node root;
	private class Node
	{/* see above*/}
	public Vaule get(Key,key)
	{/*see next*/		}
	public void put(Key key,Vaule val)
	{/*see next*/		}
	public void delete(Key key){}
	public Iterable<Key> iterator(){}
}

Get. Return Vaule corresponding to given key, or null if no such key.


public Vaule get(Key key){
	Node cur=root;
	int cmp;
	while(cur!=null){
		cmp=cur.key.CompareTo(Key));
		if(cmp>0) 
			cur=cur.left;
		if (cmp<0) {
			cur=cur.right;
		}
		else 
			return cur.Vaule;
	}
	return null;
}

Put .Associate value with key.(Tricky and recursive)

Search for key, then two cases: ・Key in tree ⇒ reset value. ・Key not in tree ⇒ add new node


public void put(Key key,Vaule val){
	root=put(root,key,val);
}
private Node put(Node node,Key key,Vaule val){
	if (node==null) { //如果没有节点，则新建节点，如果原来不含该节点，最终都到这步
		return new Node(key,val);
	}
	else{
		cmp=key.CompareTo(node.key);
		if (cmp>0) 
			node.right=put(node.right,key,val);
		else if (cmp < 0) 
			node.left=put(node.left,key,value);
		else 
			node.value=val;	
							
		}
	return node;
}

Ordered Operations

如何求最大/最小值？很简单，我们可以根据二叉查找树的定义，判定最左的子节点即为最小值，最右的为最大值。

如何写Floor和Ceiling 函数？(Floor. Largest key ≤ a given key.Ceiling. Smallest key ≥ a given key.) Q. How to find the floor / ceiling? Case 1. [k equals the key at root] The floor of k is k. Case 2. [k is less than the key at root] The floor of k is in the left subtree. Case 3. [k is greater than the key at root] The floor of k is in the right subtree (if there is any key ≤ k in right subtree); otherwise it is the key in the root.

public Key floor(Key k){
    
    Node X=floor(root,k);
    if (root == null) return null;
    return X.Key;
}
private Node floor(Node X,Key k){
    Node Y;
    if(X=null) return null;
    int cmp=k.compareTo(X.key);
    if(cmp<0)
        retrun Y=floor(X.left,k);
    else if(cmp==0)    return X;
    else {
        if (floor(X.right,k)!=null)
            return floor(X.right,k);
        else return X;  
    }
}

求数的大小：方法：在每个节点存储字数节点个数的值，使用size函数，使得它返回该节点的count值，这样的话，节点必须新加一个变量count，size函数这么写：
1
2
3
4
5
6
7
public class Node{
private Key key;
private Value val;
private Node left;
private Node right;
private int count;
}

public int size(){
    return size(root);
}
private int size(Node X){
    if(X==null) return null;
    return X.count;
}

这样put函数里应该多加这么一句：


    public void put(Key key,Vaule val){
        root=put(root,key,val);
    }
    private Node put(Node node,Key key,Vaule val){
        if (node==null) { //如果没有节点，则新建节点，如果原来不含该节点，最终都到这步
            return new Node(key,val);
        }
        else{
            cmp=key.CompareTo(node.key);
            if (cmp>0) 
                node.right=put(node.right,key,val);
            else if (cmp < 0) 
                node.left=put(node.left,key,value);
            else 
                node.value=val;                               
            }
            //return 前添加一句count值
            node.count=1+size(node.left)+size(node.right);
            return node;
    }
java    
4. 排序统计问题（Rank）
   Q. How many keys < k  ?
    ```java
    public int rank(Key k){
         int num=rank(root,k);
         return num;
    }
    private int rank(Node X,Key k){
        if (X==null) return 0;
        int cmp =k.compareTo(X.key);
        if (cmp==0) return size(X.left)//注意，size函数包括自己
        else if (cmp<0) return rank(X.left,k);
        else return 1+rank(X.left,k)+rank(X.right,k);
    }

迭代写法

方法，用队列实现，先存左边的node，再存root及节点，再存右边的节点。

public Iterable<Key>Keys(){
    Queue<Key> q = new Queue<Key>();
    inorder(root,q);
    return q;
}
private void inorder(Node X,Queue<Key>,q){
    if(X==null) return;
    inorder(X.left,q);
    enquue(X.Key);
    inorder(X.right,q);
}